/*
 *https://leetcode.cn/problems/count-numbers-with-unique-digits
 *357. 统计各位数字都不同的数字个数
    辛泽豪 2024.9.18
 *数位DP
*/

class Solution {
public:
    // 函数 countNumbersWithUniqueDigits 接受一个整数 n 作为参数，
    // 返回从 0 到 10^n - 1 的所有整数中，拥有不重复数字的整数的数量。
    int countNumbersWithUniqueDigits(int n) {
        // 创建一个大小为 n+1 的动态规划数组 dp 来存储每个长度下的结果
        vector<int> dp(n + 1);
        
        // 初始化 dp[0] 为 1，表示当 n=0 时，只有一个数（即 0）满足条件
        dp.at(0) = 1;
        
        // factor 表示在当前位上可以选择的不同数字的数目
        int factor = 9; // 除了最高位外，每位都可以从 0-9 中选择，但不能与前面相同
        
        // product 用于累积乘积，初始化为 9，因为第一位可以是 1-9 中任选一个
        int product = 9;
        
        // 从 i=1 开始遍历到 n，i 表示数字的长度
        for (int i = 1; i <= n; ++i) {
            // 当前长度 i 的结果等于前一个长度的结果加上 product
            // 这是因为我们可以从前一个长度的数后添加一个新数字来形成当前长度的数
            dp.at(i) = dp.at(i - 1) + product;
            
            // 更新 product 为 product * factor，表示增加一位后的可能组合数量
            product *= factor;
            
            // 每次循环减少 factor，因为下一位可选数字减少了 1
            --factor;
        }
        
        // 返回长度为 n 的数字中具有唯一不同数字的整数数量
        return dp.at(n);
    }
};